package com.zhang.sort.cmp;

import com.zhang.sort.Sort;

/**
 * @author 张吉鑫
 * @Description 归并排序
 * @date 2021/4/15 16:02
 */
public class MergeSort<E> extends Sort<E> {
    private E[] leftArray;

    /**
     * 执行流程
     * ① 不断地将当前序列平均分割成2个子序列
     *   直到不能再分割（序列中只剩1个元素）
     * ② 不断地将2个子序列合并成一个有序序列
     *   直到最终只剩下1个有序序列
     * 合并思路
     * ① 先将左边的元素 复制到新的数组
     * ② 跟右边数组进行比较 最小的元素放入原来数组的头节点
     */
    @Override
    protected void sort() {
        leftArray = (E[]) new Object[array.length >> 1];
        sort(0, array.length);
    }

    private void sort(int begin,int end){
        if (end - begin < 2){
            return;
        }
        int mid = (begin + end) >> 1;
        sort(begin, mid);
        sort(mid, end);
        merged(begin, mid, end);
    }

    /**
     * 合并元素
     * li 为新数组的头索引 le 为新数组的元素长度
     * ri 分割数组后的 右边数组的头索引 re 为右边数组的长度
     * ai 为合并数组的开始索引 两个数组比较后 最小的元素存储的索引位置
     * @param begin 合并数组的开始索引
     * @param mid 合并数组的中间索引
     * @param end 合并数组的尾部索引
     */
    private void merged(int begin,int mid,int end){
        int li = 0,le = mid - begin;
        int ri = mid,re = end;
        int ai = begin;

        for (int i = li; i < le; i++) {
            leftArray[i] = array[begin + i];
        }

        while (li < le){
            if (ri < re && cmpElement(array[ri], leftArray[li]) < 0){
                array[ai++] = array[ri++];
            }else {
                array[ai++] = leftArray[li++];
            }
        }

    }
}
